#include <iostream>
using namespace std;

template<class T>
class List
{
private: // 成员属性
	T* list;
	int length;
	int capacity;
public: // 构造函数与析构函数
	List()
	{
		capacity = 10;
		list = new T[capacity];
		length = 0;
	}
	List(T data) : List()
	{
		list[length++] = data;
	}
	~List()
	{
		capacity = 0;
		length = 0;
		if (list == nullptr)
			return;
		delete[] list;
		list = nullptr;
	}
public: // 尾插尾删、头插头删
	void push_back(T data)
	{
		if (length == capacity)
			moreCapacity();
		list[length++] = data;
	}
	void pop_back()
	{
		if (empty())
			return;
		length--;
	}
	void push_front(T data)
	{
		if (length == capacity)
			moreCapacity();
		int current = length;
		while (current)
		{
			list[current] = list[current - 1];
			current--;
		}
		list[current] = data;
		length++;
	}
	void pop_front()
	{
		if (empty())
			return;
		int current = 1;
		while (current != length)
		{
			list[current - 1] = list[current];
			current++;
		}
		length--;
	}
	void deleteDest(T data) // 指定内容删除
	{
		int index = find(data);
		if (index == -1)
			return;
		while (index + 1 != length)
		{
			list[index] = list[index + 1];
			index++;
		}
		length--;
	}
	void deleteAllDest(T data) // 利用快慢指针在O(n)内 删除所有对应的内容
	{
		int fast = 0, slow = 0;
		while (fast != length)
		{
			if (list[slow] != data)
				slow++;
			list[slow] = list[++fast];
		}
		length = length - (fast - slow);
	}
	void clear() // 清空
	{
		delete[] list;
		list = nullptr; // 记得置为空指针，避免析构时重复释放
		capacity = 0;
		length = 0;
	}
public:
	bool empty() // 判空
	{
		return length == 0;
	}
	int getSize()
	{
		return length;
	}
	int getCapacity()
	{
		return capacity;
	}
	int find(T data)
	{
		for (int i = 0; i < length; ++i)
			if (list[i] == data)
				return i;
		return -1;
	}
	T& operator[](int index) // 运算符重载，方便外面用 []
	{
		return list[index];
	}
private: // 没必要让使用者看到的接口
	void moreCapacity() // 扩容
	{
		T* newSpace = new T[capacity + 10];
		for (int i = 0; i < capacity; ++i)
			newSpace[i] = list[i];
		delete list;
		list = newSpace;
		capacity += 10;
	}
};
int main()
{
	List<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
    list.deleteAllDest(3);
	for (int i = 0; i < list.getSize(); ++i)
		cout << list[i] << " ";
	return 0;
}